1. Field of the Invention
The present invention relates to a method and apparatus for optimizing flow control of message traffic on a local area network (LAN). More particularly the present invention relates to a flow control method and apparatus that can be added to existing networks without disruptively interfering with existing network protocols or operations.
2. Description of the Related Art
A local area network, or LAN, is a system that provides interconnection and a communication protocol between a number of independent computing stations within a proximate area, such as a single building or a campus of adjacent buildings. An overview of local area network concepts and technology is set forth in William Stallings' book entitled Local Networks, Third Edition, MacMillan Publishing Company, 1990, and is hereby incorporated herein by reference.
Networks are typically constructed from network condensers such as routers, switches, bridges, repeater units, and hubs. End users that connect to the network, e.g., a desktop computer, provide a network node. Nodes are typically workstations, servers, printers, etc., and condensers concentrate the nodes into a common network. Routers and switches/bridges, intelligently or blindly, direct network traffic. At the most basic level, network condensers are devices that interconnect network nodes attached to a structured wiring plant. Network condensers are most often employed to concentrate, amplify, and restructure incoming signals; they allow the different nodes to communicate with one another by repeating signals they receive to some or all of the nodes attached to them, which is the basic function common to all the network repeater units mentioned above.
For simplicity, the term repeater unit will usually be used throughout the remainder of this specification to refer to network condensers performing the basic function of retransmitting a data packet received from a node though with the understanding that some types of network condensers perform more complex processing of network node transmissions.
Data is communicated over the network in units that are usually referred to as "frames" or "packets." In addition to data to be transmitted, each packet includes protocol control information such as the address of the packet source (transmit station) and the address of the packet destination (receive station).
As indicated above, there are several accepted terms that describe different kinds of network condensers in terms of their processing of network node transmissions. For example, routers, switches, bridges, repeater units and hubs are all physical units that are used to interconnect nodes on a LAN or to interconnect LANs themselves. A repeater is the simplest type of interconnect device since a repeater merely replicates incoming packets on its remaining ports. Switches or bridges buffer data packets that they receive and look at the address field of each data packet to make a routing decision, sending packets only out of selected ports. Routers look at both the address and the protocol header of each packet to determine the routing for each packet. All of these condenser devices typically include several ports, sometimes numbering in the hundreds. The ports provide the physical means to build a network; specifically, the ports are most often used to provide network connection points for the nodes. However, as indicated above, a port can also be used to connect one network condenser to another.
The interconnection pattern or layout of a network is called a topology. One such well known topology has a star configuration. In a star topology network, each node has a dedicated communication medium connected to a port on the repeater unit, e.g. each node has its own cable connection to the repeater unit. A packet transmitted by the node propagates through the medium and is received by the repeater unit which recovers the data contained in the packet and retransmits it to the destination station to which it is addressed. Similarly, the repeater unit transmits packets which propagate through the medium and are received an attached node or another repeater unit.
LANs utilize one of two types of data transmission techniques: either baseband or broadband. Baseband transmission uses signaling which can encompass the entire frequency range of the transmission medium and can be implemented with all media types but is typically implemented with twisted pair, coaxial, or fiber optic cable. Broadband transmission uses signaling where the signal is encoded within a limited frequency range. The signal used to modulate a broadband signal to a specific frequency range is referred to as a "carrier." By restricting the frequency range, broadband systems can multiplex many independent communication channels onto a single medium.
In a baseband LAN, digital data is converted to signals typically using Nonreturn-to-zero (NRZ) encoding. The signals are transmitted onto the medium encoded as voltage pulses typically using the well known Manchester encoding method. Transmission is bi-directional; that is, a signal inserted at any point on the medium propagates in both directions to the ends of the medium where it is absorbed. Baseband systems can extend only a limited distance, usually about a 1.0 KM maximum for copper based media without regeneration, due to attenuation of the signal. Fiber optic baseband systems are cable of distances of approximately 40 KM.
Because of the wide variety of physical, electrical, optical and procedural characteristics available to designers of equipment for local area networks, it has become widely acknowledged that certain standards must be observed. For example, the International Organization for Standardization (ISO) has developed a voluntary Open Systems Interconnection (OSI) model which defines a general computer networking system architecture. In principle, an "open" system may be designed in a unique manner but still be able to communicate with other open systems, provided that the implementation conforms to a minimal set of OSI standards. The OSI model is general and applies to both wide area networks and LANs.
The problem of complexity in computer network communication is best handled by using a layered architecture approach, in which all networking functions are partitioned into several groups, called layers, in such a way that upper layers use services provided (or functions performed) by lower layers. The OSI model implements the layered architecture concept and defines a number of layers, the particular functions performed by each layer, and interlayer interfaces. The partitioning of all networking functions into layers is guided by two contradictory constraints. When more layers are used, each becomes smaller and simpler. On the other hand, the use of many layers creates many interlayer interfaces, and the processing overhead necessary to handle additional interfaces eventually offsets the benefits gained by layer simplification.
The OSI model partitions networking functions into seven layers, as shown in FIG. 1. These layers include the Physical (or medium) layer 1, the Data-link layer 2, the Network layer 3, the Transport layer 4, the Session layer 5, the Presentation layer 6, and the Application layer 7. As noted above, the OSI model also defines the interlayer interfaces. A message to be sent from a program running on a first computer to a program running on a second computer must be passed from the application layer 7 of the first computer all the way down to the physical layer 1 of the first computer, across the network medium, and up from the physical layer 1 of the second computer, all the way up to the application layer 7 of the second computer. Thus, under the OSI model networked computers must implement the seven layer "protocol stack" in order to allow applications to communicate.
Once the OSI model was adopted, more refined standards defining each of the OSI layers could be developed. For example, if a standard is established for the data-link layer 2, specifying its functions and upward and downward interfaces, any product that implements the standard in any way is compatible with other products that obey the same standard. Several standardization organizations developed implementation standards for different OSI layers.
A number of local area network protocol standards that implement one or more layers of the OSI model have been developed by the Institute of Electrical and Electronics Engineers (IEEE) 802 committee. One of the best known standards published by the IEEE 802 committee, the IEEE 802.3 standard, is based on the Ethernet local area network developed by Xerox Corporation in the mid-1970s. This standard, available from the IEEE, is hereby incorporated herein by reference. The Ethernet architecture was used as the basis for defining a protocol for bus or tree topology LANs that is also frequently utilized with star topology LANs that anticipate that stations on the network will be located a relatively short distance (no more than 100 meters) from the repeater unit. Within the IEEE 802.3 10BASE-T standard, a repeater unit is a device which allows the star topology network to mimic the logical operation of its bus topology counterpart.
As discussed below, the IEEE 802.3 standard defines a protocol that implements the carrier sense multiple access with a collision detection (CSMA/CD) method for bus contention. The standard also defines an implementation of an ISO compliant medium access control (MAC) function for transmitting packets to and receiving packets from the transmission medium (Physical layer 1) as well as the packet structure and the interaction that takes place between other entities that implement the MAC function on the network.
Since different media types may be used by the same underlying MAC, the standard provides a common interface called the Attachment Unit Interface (AUI). Different media access units (MAUs) that implement the required functions for interfacing to a given media type may be connected to the AUI. Examples include: 10BASE-2 MAUs which connect a MAC or a repeater unit to coaxial cable; and 10BASE-T MAUs which connect a MAC to two copper twisted pair cables. The MAC and its associated AUI are collectively referred to as an end station, node or sourcing station. The AUI governs 10 Mb/s systems. A similar interface definition called the Media Independent Interface provides similar capabilities to both 100 Mb/s and 10 Mb/s systems.
As stated above, in a star topology network, a transmission from a node on the network is first transmitted to the repeater unit which either retransmits the packet through all of the repeater unit's ports so that it is received by all other end stations or the repeater unit performs some routing and directs the packet to ports corresponding to the contents of the packet. A conventional repeater is transparent to the rest of the network system. It does no buffering or routing and does not isolate one segment from the rest of the network. Thus, if two stations on different segments attempt transmission at the same time, their transmissions will collide.
FIG. 2 depicts an example of an Ethernet 802.3 network with a point-to-point star topology. Multiport repeater 100 is shown terminating three nodes 20, 30, 40 each with its own network communication segment (22, 32, 42 respectively). Each network segment 22, 32, 42 terminates one of the repeater interfaces 120, 130, 140 on repeater 100. The network communication segments 22, 32, 42 together constitute the network medium 22, 32, 42 in FIG. 2.
Though the IEEE 802.3 CSMA/CD protocol defines a "random access" or "contention" technique for multiple stations sharing a network medium where any station is allowed to transmit without permission from any other network device, it also is used to address the problem of how both the end station and repeater unit will share a common transmission medium when the end station and repeater unit contend with one another to transmit on the shared medium.
According to the well-known carrier sense multiple access (CSMA) technique, a station 20, 30, 40 wishing to transmit first "listens" to the medium 22, 32, 42 to determine if another transmission is occurring. If the station 20, 30, 40 determines that the medium 22, 32, 42 is in use, then the station 20, 30, 40 idles for some pseudo-random time and then re-attempts the transmission. The pseudo-random time is a calculated value determined by a "backoff algorithm". If the medium 22, 32, 42 is idle, then the station 20, 30, 40 transmits. If two or more stations 20, 30, 40 (or the repeater 100) transmit at the same time, then a collision occurs. To account for collisions, the transmitting station (20 for example) waits a period of time after transmitting for an acknowledgment that its transmission has been received by the destination station (30 for example). If no acknowledgement is received, then the transmitting station 20 assumes that a collision has occurred and retransmits.
Although the CSMA technique is an efficient method for managing transmission on a shared medium, it does have deficiencies. For example, when two packets collide, the medium 22, 32, 42 remains unstable for the duration of transmission of both packets. For long packets, the amount of transmission bandwidth wasted before retransmission is permitted can be considerable.
This bandwidth waste can be reduced if a transmitting station 20 continues to listen to the medium 22, 32, 42 while it is transmitting. The protocol for this more sophisticated procedure, known as carrier sense multiple access with collision detection (CSMA/CD) are as follows. If a station 20 for example, wishing to transmit senses that the medium 22, 32, 42 is idle, it then transmits. If the station 20 senses that the medium 22, 32, 42 is busy, it continues to listen to the medium 22, 32, 42 until it senses that the medium 22, 32, 42 is idle and then transmits. If the station 20 detects a collision (two simultaneous transmissions) during transmission, then it transmits a brief jamming (JAM) signal to assure that all stations on the network know that there has been a collision; then it ceases transmission. After transmitting the jamming signal, the station waits a pseudo-random period of time computed using the backoff algorithm and then re-attempts the transmission.
One important dimension of a star topology network is determined by the number of repeaters between end stations and the number of network medium "segments" 22, 32, 42 terminating on the repeater 100 wherein a segment 22, 32, 42 connects the repeater 100 to a single end station or node 20, 30, 40. A repeater unit may include two or more MAUs and associated logic joined together and connected to two or more different segments of the network medium.
FIG. 3 is a more detailed diagram of the connection between a repeater 100 and a node 20. Network segment 22 is the bidirectional communication medium between MAU 26 of node 20 and repeater interface 120 of multiport repeater 100. MAU 26 decodes signals received on segment 22 into digital input data Din for digital terminating equipment (DTE) 28. Some typical examples of common DTE devices are personal computers and printers. MAU 26 also encodes digital output data Dout from DTE 28 and transmits it onto segment 22. DTE 28 also receives control information CONTROL from MAU 28. Examples of signals that may comprise control information CONTROL are carrier received, clear to send data, not clear to send data, and collision detect.
FIG. 4 illustrates a detailed example of an IEEE 802.3 multi-port repeater system 100. Each repeater interface 120, 130 and 140 consists of a transceiver and a port, such as transceiver 122 and port 124 of repeater interface 120. A Manchester encoded data packet received at one of multiple transceivers (XCVR) such as XCVR 122 of the system 100 is processed by the associated port logic 124 and then provided via a multiplexor 110 to a decoder 150. The decoder 150 recovers NRZ encoded data and a clock signal from the Manchester encoded input. Data is placed on a CONTROL BUS for processing by a central state machine 160, which implements the repeater's protocol facilities, aided by a set of central counters 170. Information generated by the central state machine 160 may be provided to a set of display devices and drivers 180. Data recovered from the decoder 150 is entered, via a RX DATA PATH BUS, into an elasticity first-in-first-out (FIFO) buffer 190. From the FIFO buffer 190, the data is read, Manchester encoded, and then retransmitted to all the other network segments terminating on the repeater, such as the segments connected to the other repeater interfaces 130, 140.
The IEEE 802.3 standard provides for a variety of medium and data-rate options within the protocol. To distinguish implementations using different alternatives, the following notation was originally used: EQU (data rate in Mbps).vertline.(medium type)-(max. segment length/100M)
Thus, an IEEE 802.3 network with a data rate of 10-Mbps, a baseband medium and a maximum segment length of 500 meters is referred to as a 10BASE-5 network. Unfortunately, there are many exceptions to this notation such as 10Base-T.
The IEEE 802.3 10BASE-5 standard specifies use of a 50-ohm coaxial cable of a defined thickness as the transmission medium and a data rate of 10 Mbps using digital signaling with Manchester encoding. It is these parameters in part that result in the maximum cable length being limited to 500 M/segment.
The IEEE 802.3 10BASE-2 standard provides a lower-cost network configuration well suited for personal computer networks and commonly referred to as "Cheapernet". As with a 10BASE-5 network, a 10BASE-2 network uses 50-ohm coaxial cable and Manchester encoding at a data rate of 10 Mbps.
The difference between a 10BASE-5 and a 10BASE-2 Cheapernet network is the use in a Cheapernet network of a thinner, more flexible cable which enables expanded, simpler installation options. However, the thinner cable suffers greater signal attenuation and lower noise resistance and, thus, only supports relatively shorter segment lengths.
The IEEE 802.3 network standard includes a "heartbeat" or "still active and connected" function. This is a signal sent from the MAU to the station that confirms that the MAU collision signal circuitry is working and connected to the DTE station. Without this signal, which is referred to as the signal-quality-error signal, the station is unsure whether the frame was actually sent without a collision or whether a defective MAU failed to properly report a collision. IEEE 802.3 also includes a "jabber" function. This is a self-interrupt capability that allows a MAU to inhibit transmitted data from reaching the medium if the transmission occurs for longer than a predetermined time period.
Chapter 9 of the IEEE 802.3 specification defines the standard for a repeater unit utilizable in 10 Mbps baseband networks. As stated in the specification, network segments may be connected directly by repeater unit combinations as long as only one signal path is operative between any two points on the network and the number of repeater units in that signal path is not greater than four. The 802.3 repeater unit must be designed to receive and decode data from any network segment under defined jitter conditions and to retransmit data to all other network segments attached to it with timing and amplitude restored. Retransmission of data occurs simultaneously with reception. If a collision occurs, the repeater unit propagates the collision event throughout the network by transmitting a JAM signal. The repeater unit also detects and isolates faulty network segments.
A fundamental behavior that controls whether an IEEE 802.3 end station may transmit or not transmit is called deferral. In other words, a station will not transmit during deferral. Deferral is controlled in the MAC by the use of a carrier received signal (CRS). CRS is asserted whenever carrier activity is received at the end station regardless of whether the carrier includes data or not.
The time between the transmission of frames is referred to as the interframe gap (IFG). The IEEE 802.3 standard defines that the IFG is ninety-six bit times long. That is, the period of time required to transmit ninety-six bits.
The 802.3 standard allows two different forms of deferral: two-part deferral and one-part deferral. In two-part deferral, Ethernet MACs will defer to a CRS that is activated less than sixty-four bit times after the last successful transmission or reception. This is true because the interframe gap of ninety-six bits is divided into a first portion (typically 2/3 of the total IFG or sixty-four bits) where any carrier activity will cause deferral to continue and a second portion (typically the final 1/3 of the IFG) where the station will transmit even though a carrier signal is present. The carrier signal does not result in valid data being passed to higher protocol layers above the MAC so long as the signal does not contain a Start of Frame Delimiter (SFD) bit pattern.
Before the advent of two-part deferral, the almost obsolete one-part deferral method was used exclusively. In one-part deferral, once a station has a frame to transmit, it waits for any frame currently on the medium to complete (CRS deasserted), waits its interframe gap, and then transmits onto the medium independent of the value of CRS when the interframe gap timer expires. Only the earliest Ethernet devices were designed to function in this manner and continue to exhibit this behavior. The vast majority of network equipment currently in use implement and thus exhibit two-part deferral behavior. One-part deferral is accommodated by the IEEE 802.3 standard in that it permits the first part of a two-part deferral to be any time duration including zero. However, as indicated, the vast majority of implementations that will be encountered in the marketplace use the well defined two-part deferral algorithm with the first part being 2/3 of the interframe gap.
A simple flow control system to control the transmission of a node may be designed to handle one-part deferral implementations. However, such a system will possess some undesirable side effects. One such side effect is that a collided end station's transmission is delayed, but the collision counter in the end station's MAC is incremented. As a result, a delay determined by the backoff algorithm will take place prior to another transmission attempt of the end station's data frame. In a poorly designed network or when severe congestion occurs elsewhere in the network, an end station may reach its attempt limit before the frame ever gets transmitted causing the frame to be discarded. However, while loss of a frame is extremely undesirable, it is not catastrophic. Ultimate responsibility for end to end packet delivery resides with the transport layer 4 above the MAC. Thus, because loss of a packet through excessive collisions is always a possibility in an Ethernet network, it must be accounted for at a higher layer in the protocol stack.
One-part deferral is, at its worst, the effective equivalent of a pure collision based flow control algorithm where a collision is caused whenever there is an unwanted transmission on the wire. A downside of this approach is that the star device will not know how long the collided station's MAC will take to schedule the next transmission since this time is pseudo-randomly determined by the backoff algorithm that depends upon the collision count of the collided end station. Therefore, a flow controlling agent that collides with an end station may have to wait for a substantial and undeterministic time period before the MAC transmits again.